The invention is concerned with an error correcting code decoding system for use in digital communication networks using error correcting codes where transmission errors are corrected automatically at the receiving station.
Of various kinds of error correcting code proposed so far, Bose-Chaudhuri-Hocquenghem code (in short BCH code) has been widely used in practice for its high degree of freedom for choosing code length and number of correctable errors, and its error correcting capability achieved with relatively few check bits.
A decoding process of the BCH code word is shown, for example, in Chapter 7.3 of "Coding theory" (by Miyagawa, Iwadare, and Imai; Shokodo Publishing Co.) where a received code word (it may have a bit error or bit errors) is first input to a feedback shift register whose structure corresponds to the code generator polynomial in order to obtain the syndromes. The syndromes thus obtained make it possible to derive an error locator polynomial by means of Peterson's method or Barenkampf-Massey's methods. The roots of the error locator polynomial indicate the error bit positions, if any, of the received code word, and the correction can be performed accordingly.
Several methods for deriving an error locator polynomial from given syndromes, other than one described above, have been known.
One of them is described in the following paper. (Koga: "A new decoding method of binary BCH code.", Trans. of the Institute of Electronics and Communication Engineers of Japan, Vol J 66-A, No. 10, pp. 925/932, October 1983)
This method shows that the coeffieicnts of the error locator polynomial of a received code word are calculated with symmetrical determinants whose elements are chosen from among the syndromes. And a useful method for calculating these determinants is proposed in the following paper. (Koga, Yamasaki: "A simple method of calculating the coefficients of error location polynomial in binary BCH code.", 1984 National Convention of the Institute of Electronics and Communication Engineers of Japan, 1456, March 1984)
This method shows that a determinant of order k of the kind is calculated by adding a certain number of products of determinant of order less than k and the square of syndrome.
The conventional methods for obtaining the error locator polynomial have a drawback in common that the procedure required for deriving it becomes too much complicated to be used in practice with increasing the number of correctable errors.
Therefore, almost all the error correction systems using the BCH code that have been used so far are limited to those of one-error correction or two-error correction.